\section{Slimes}
\subsection*{题意}
给定序列 $a = [a_1 ,a_2 ,\cdots, a_n]$。

每次操作可以把\textbf{相邻}的两个元素合并，新元素的值为权值之和。每次合并的成本为新元素的值。

求把所有元素合并成一个的最小成本。

\subsection*{数据范围}
\begin{itemize}
\item $2 \leq n \leq 400$
\item $1 \leq a_i \leq 10^9$
\end{itemize}

\subsection*{题解}

本题是一道典型的\textbf{区间型}动态规划。

注意到下列事实：
\begin{enumerate}
\item 无论顺序为何，若干元素合并后的权值一定等于初始权值之和。
\item 由于只能合并相邻元素，在\textbf{任意}时刻，序列中的每个元素一定对应初始序列的某个连续段：例如 $[1,2,3,4,5]$ 经过若干次操作后变为 $[(1+2+3),(4+5)]$，则 $(1+2+3)$ 对应 $[1,2,3]$ 。

\end{enumerate}
现在我们来观察将一个序列合并成单独一个元素的过程：$[a_1 ,a_2 ,\cdots, a_n] \rightarrow s$。不难发现一定是头部若干元素合并后的结果与尾部若干元素合并后的结果的再最终合并的产物。举个例子：
$$
[1,2,3,4,5] \rightarrow [(1+2+3),(4+5)] \rightarrow 15
$$那么现在设状态 ${\texttt{dp}[l][r]}$ 表示子序列 $a_l,a_{l+1}\cdots, a_r$ 合并成单一元素的最小成本，通过枚举头尾分界位置 $m$，可以得到转移方程：
$$
{\texttt{dp}[l][r]} = \min\{{\texttt{dp}[l][m]}+{\texttt{dp}[m+1][r]}\mid l\le m< r\} + \sum_{i = l}^r a_i
$$
其中区间和部分可以通过前缀和计算，当然这里由于每个状态有 $O(n)$ 个转移，暴力计算亦可。总复杂度为 $O(n^3)$。 





\newpage
\subsection*{核心代码}
\inputminted[linenos,autogobble]{cpp}{./Code/N.cpp}
\newpage